//给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。 
//
// 
//
// 示例 1： 
//
// 
//输入: nums = [0,1]
//输出: 2
//解释: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。 
//
// 示例 2： 
//
// 
//输入: nums = [0,1,0]
//输出: 2
//解释: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// nums[i] 不是 0 就是 1 
// 
//
// 
//
// 
// 注意：本题与主站 525 题相同： https://leetcode-cn.com/problems/contiguous-array/ 
//
// Related Topics 数组 哈希表 前缀和 👍 158 👎 0


package LeetCode.editor.cn;


import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2025-01-15 17:14:19
 * @description LCR 011.连续数组
 
 */
 
public class A1NYOS {
    public static void main(String[] args) {
    //测试代码
    A1NYOS fun = new A1NYOS();
    Solution solution= fun.new Solution();
        System.out.println(solution.findMaxLength(new int[]{0, 1}));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //超时
    public int findMaxLength1(int[] nums) {
        int len = nums.length;
        int []ar=new int[len];
        ar[0]=nums[0];
        int res=0;
        for (int i = 1; i < len; i++) {
            ar[i]=ar[i-1]+nums[i];
            if(ar[i]*2==i+1) res=i+1;
            for (int j = ar[i]; j >=res/2; j--) {
                if(i-j*2>=0&&ar[i-j*2]==ar[i]-j)res=Math.max(res,j*2);
            }
        }
        return res;
    }
    //把0转化为-1，用于计算区间和为0，
    public int findMaxLength(int[] nums) {
        int res=0;
        Map<Integer,Integer> map=new HashMap<>();
        int sum=0;
        map.put(0,-1);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int num=nums[i];
            if(num==1){
                sum++;
            }else {
                sum--;
            }
            if(map.containsKey(sum)){
                Integer pre = map.get(sum);
                res=Math.max(res,i-pre);
            }else {
                map.put(sum,i);
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
